package dp.一维数组;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/
 *
 * 题解：https://mp.weixin.qq.com/s/7QFapCuvi-2nkh6gREcR9g
 *
 * 这题和53很像，dp方程不是最后结果，而是以当前元素结尾的最值，最后返回的结果还要遍历当前值之前的dp
 */
public class _300_最长递增子序列 {

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        // dp的意思是以nums[i]结尾的最大递增子序列.默认值是1，就是自己
        int[] dp = new int[nums.length];
        // 这个很关键，表明以这个字段结果的最长子序列最长是1
        Arrays.fill(dp, 1);


        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }

        int result = 0;

        for (int i = 0; i < dp.length; i++) {
            result = Math.max(result, dp[i]);
        }

        return result;
    }
}
